package tree.structure.rbtree2;


import java.util.Random;

/**
 * 红黑树基本性质
 * 1.根节点和外部节点为黑
 * 2.从根节点到外部节点不存在连续的红色节点
 * 3.从根节点到外部节点的黑节点个数相同
 * <p>
 * 红黑树-插入操作
 * 讨论插入节点是红色还是黑色：如果是黑色，意味着性质3必然被打破。如果是红色，父节点为黑色时可不用调整。
 * 综合来看插入节点默认为红色时调整操作较少
 * <p>
 * 1.如果插入后父节点为黑色，则不用调整
 * 2.如果插入后父节点为红色，需要枚举所有情况调整
 * LLR
 * LLB
 * LRR
 * LRB
 * RLR
 * RLB
 * RRR
 * RRB
 * <p>
 * 第一个位置表示父节点的是左节点还是右节点，第二个位置表示插入节点是左孩子还是右孩子，第三个位置表示父节点的兄弟节点的颜色
 */

public class RBTree {

    private RBTreeNode root;
    private RBTreeNode nil = null;

    /**
     * 插入新节点
     *
     * @param key
     */
    public void put(int key) {
        RBTreeNode insertNode = new RBTreeNode(key);
        RBTreeNode pre = root;
        RBTreeNode cur = root;
        if (isNull(root)) {
            root = insertNode;
        } else {
            while (isNotNull(cur)) {
                pre = cur;
                if (cur.getKey() > key) {
                    cur = cur.left;
                } else if (cur.getKey() < key) {
                    cur = cur.right;
                } else if (cur.getKey() == key) {
                    // 相同的 key 不处理
                    return;
                }
            }
            // 插入新节点到 pre
            if (pre.getKey() > key) {
                pre.setLeft(insertNode);
            } else {
                pre.setRight(insertNode);
            }
            // 设置父节点
            insertNode.setParent(pre);
            insertBalance(insertNode);
        }
        // 保证根节点为 黑
        root.setBlackColor();
    }

    /**
     * 插入平衡
     *
     * @param insertNode
     */
    private void insertBalance(RBTreeNode insertNode) {
        // 插入节点的父节点是 黑 ，不用调整
        if (isBlackColor(insertNode.getParent())) {
            return;
        }
        RBTreeNode parent = insertNode.getParent();
        RBTreeNode grandParent = parent.getParent();
        // LXx
        if (parent.getParent().getLeft() == parent) {
            // LXb
            if (isBlackColor(grandParent.getRight())) {
                // LLb
                if (parent.getLeft() == insertNode) {
                    // 变色
                    grandParent.setRedColor();
                    parent.setBlackColor();
                    // 旋转：左旋
                    rightRotate(grandParent);
                }
                // LRb
                else if (parent.getRight() == insertNode) {
                    // 转换为 LLb
                    insertNode = parent;
                    leftRotate(insertNode);

                    // 变色
                    grandParent.setRedColor();
                    parent.setBlackColor();
                    // 旋转：左旋
                    rightRotate(grandParent);
                }
            }
            // LXb
            else {
                // LLr
                if (parent.getLeft() == insertNode) {
                    parent.setNodeColor(RBTreeNode.NodeColor.RB_NODE_COLOR_BLACK);
                    if (grandParent.getRight() != null) {
                        grandParent.getRight().setBlackColor();
                    }
                    grandParent.setRedColor();
                    insertBalance(grandParent);
                }
                // LRr
                else if (parent.getRight() == insertNode) {
                    // 转换为 LLr
                    insertNode = parent;
                    leftRotate(insertNode);

                    parent.setNodeColor(RBTreeNode.NodeColor.RB_NODE_COLOR_BLACK);
                    if (grandParent.getRight() != null) {
                        grandParent.getRight().setBlackColor();
                    }
                    grandParent.setRedColor();
                    insertBalance(grandParent);
                }
            }
        }
        // RXx
        else if (parent.getParent().getRight() == parent) {
            // RXb
            if (isBlackColor(grandParent.getLeft())) {
                // RLb
                if (parent.getLeft() == insertNode) {
                    // 转换为RRb
                    insertNode = parent;
                    rightRotate(insertNode);

                    grandParent.setRedColor();
                    parent.setBlackColor();
                    // 旋转：左旋
                    leftRotate(grandParent);
                }
                // RRb
                else if (parent.getRight() == insertNode) {
                    // 变色
                    grandParent.setRedColor();
                    parent.setBlackColor();
                    // 旋转：左旋
                    leftRotate(grandParent);
                }
            }
            // RXr
            else {
                // RLr
                if (parent.getLeft() == insertNode) {
                    // 转换为RRr
                    insertNode = parent;
                    rightRotate(insertNode);

                    parent.setNodeColor(RBTreeNode.NodeColor.RB_NODE_COLOR_BLACK);
                    if (grandParent.getLeft() != null) {
                        grandParent.getLeft().setBlackColor();
                    }
                    grandParent.setRedColor();
                    insertBalance(grandParent);
                }
                // RRr
                else if (parent.getRight() == insertNode) {
                    parent.setNodeColor(RBTreeNode.NodeColor.RB_NODE_COLOR_BLACK);
                    if (grandParent.getLeft() != null) {
                        grandParent.getLeft().setBlackColor();
                    }
                    grandParent.setRedColor();
                    insertBalance(grandParent);
                }
            }
        }
    }

    /**
     * node节点处右旋
     *
     * @param node
     */
    private void rightRotate(RBTreeNode node) {
        // 存放当前节点node的数据，因为当前节点要挂在右儿子的的left
        RBTreeNode newNode = new RBTreeNode(node.getKey());
        // 保留颜色
        newNode.setNodeColor(node.getNodeColor());
        if (isNotNull(node.getRight())) {
            // 设置原来左节点的父节点为新节点
            node.getRight().setParent(newNode);
        }
        newNode.setRight(node.getRight());
        if (isNotNull(node.getLeft().getRight())) {
            node.getLeft().getRight().setParent(newNode);
        }
        newNode.setLeft(node.getLeft().getRight());

        node.setKey(node.getLeft().getKey());
        node.setNodeColor(node.getLeft().getNodeColor());
        node.setLeft(node.getLeft().getLeft());
        if (isNotNull(node.getLeft())) {
            node.getLeft().setParent(node);
        }

        node.setRight(newNode);
        newNode.setParent(node);
    }

    /**
     * node节点处左旋
     *
     * @param node
     */
    public void leftRotate(RBTreeNode node) {
        // 存放当前节点node的数据，因为当前节点要挂在右儿子的的left
        RBTreeNode newNode = new RBTreeNode(node.getKey());
        // 保留颜色
        newNode.setNodeColor(node.getNodeColor());
        if (isNotNull(node.getLeft())) {
            // 设置原来左节点的父节点为新节点
            node.getLeft().setParent(newNode);
        }
        newNode.setLeft(node.getLeft());
        if (isNotNull(node.getRight().getLeft())) {
            node.getRight().getLeft().setParent(newNode);
        }
        newNode.setRight(node.getRight().getLeft());

        node.setKey(node.getRight().getKey());
        node.setNodeColor(node.getRight().getNodeColor());
        node.setRight(node.getRight().getRight());
        if (isNotNull(node.getRight())) {
            node.getRight().setParent(node);
        }

        node.setLeft(newNode);
        newNode.setParent(node);
    }

    public boolean isNull(RBTreeNode node) {
        return node == null;
    }

    public boolean isNotNull(RBTreeNode node) {
        return node != null;
    }

    public boolean isBlackColor(RBTreeNode node) {
        return node == null || node.getNodeColor() == RBTreeNode.NodeColor.RB_NODE_COLOR_BLACK;
    }

    public static void main(String[] args) {
        RBTree rbTree = new RBTree();
        //int[] data = new int[]{10, 50, 60, 62, 65, 70};
//        int[] data = new int[]{70, 65, 62, 60, 50, 10};
//        for (int datum : data) {
//            rbTree.put(datum);
//        }
        for (int i = 1; i < 100000000; i++) {
            int k = new Random().nextInt(1000);
            //System.out.println("k = " + k);
            rbTree.put(k);
        }
        System.out.println();
    }
}
